import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MillerRabin {
	static int times=20;
	static int e=65537;
	static List<BigInteger> judges= new ArrayList<>();
	static Random random=new Random();
	static {
		while (judges.size()<times) {
			BigInteger judge=new BigInteger(16, random);
			judges.add(judge);
		}
	}
	public static void main(String[] args) throws NoSuchAlgorithmException, InterruptedException {
		/*
		 * ExecutorService executor = Executors.newFixedThreadPool(12); for (int i = 0;
		 * i < 12; i++) { executor.execute(new FindFakePrime()); }
		 * executor.awaitTermination(1, TimeUnit.HOURS);
		 */		
		//publicKey(new BigInteger("168605283348056001100080266772705175121"),new BigInteger("288078355147691254494623790383250035669"));
		//getPrime(1024);
		BigInteger p=new BigInteger("11547972830505162319816514855056719888039227293849857172988956978721808734992864609969850873015815772172720688583512835426718901224794648121508206280169612751296956133952787382385675128386829336662749752460703086409653919305284868782558764970514392542770628054161290829839915355030968410634161330598269303657");
        BigInteger q=new BigInteger("143814813074391344452425359152336280891865590594529039743439525277873556629034378097115167513650261036038375160058459046441469553194378539301754686829009501947033623704274150146923437592588696095320476486034566718512227317204599602026678962433432020604211003757839777848617770247072234827244758714875681092453");
		privateKey(p,q);
		getd(new BigInteger("65537"),p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)));
		//millerRabin(new BigInteger("9746347772161"));
		//encrypt(new BigInteger("2"),new BigInteger("24160283975843255741994567481215996925127476338158089364809145103561079416870799100154927326021544827979051553614754686803445423930030084275795244637920300820941511958169542749439498292157275940599743913206796409390536192694883310507314217380223565926348694843087942529887228530722536817378102700244822929155066228056554241731308684404651292499267252416064952112734939819670309469385476173300704018035999328039693321591372309877827172522149765515783599379766814996838267342547146739660753817637134719194004304353099327939147104974978578345085752275145639533513670007313700137812476635777321335080604406981210570238087"),new BigInteger("65537"));
		//decrypt(new BigInteger("13517236345347370207661340003195790802895405540733742834226827030044086172303545605513924297300630995224417205044385882561704459365338530375182636537976771117310331421405927851944922444402907511096336619717941335021190221128286379632173093004390529705190044701222140274139123274170698548205371540060066770672505916583762633793026357663445657582878039855112049299550524666904043385296094272020109328530897010273538391486121067530407989279347981635371899154764835613026283930682205330743296041431002319915708219095087968444842436705335934282726355244906299041063880485477515965521225005588023240103262733717445469027808"),new BigInteger("24160283975843255741994567481215996925127476338158089364809145103561079416870799100154927326021544827979051553614754686803445423930030084275795244637920300820941511958169542749439498292157275940599743913206796409390536192694883310507314217380223565926348694843087942529887228530722536817378102700244822929155066228056554241731308684404651292499267252416064952112734939819670309469385476173300704018035999328039693321591372309877827172522149765515783599379766814996838267342547146739660753817637134719194004304353099327939147104974978578345085752275145639533513670007313700137812476635777321335080604406981210570238087"),new BigInteger("20036184660376290485945416216855965834271912644443477073674062535339497784563344844796379147188167926524885971877899770019489125083496880851877131178890830364804174358400821649328421077845307953851962733765497121479097945785844758320834455568841277569877345083263342485914382267189066878625812621241529612273386028967149292077777430640118168435742044895618658621581092648202497754535132101749652958799650071930793126650809003497449458304056496587224565768184121433843712972928571056813009294358855273903141866648617930943781020470945698069481866647232694836511243462633108866110749124792389305984053793904831773683473"));
	}
	
	public static void getd(BigInteger e,BigInteger z){
        List<BigInteger> list=new ArrayList<>();
        int flag=0;
        if (e.compareTo(z)==1) {
            list.add(e);
            list.add(z);
            list.add(e.mod(z));
            flag=1;
        }else{
            list.add(z);
            list.add(e);
            list.add(z.mod(e));
            flag=-1;
        }
        
        while (!list.get(list.size()-1).equals(BigInteger.ONE)) {     
            BigInteger last1=list.get(list.size()-1);
            BigInteger last2=list.get(list.size()-2);
            list.add(last2.mod(last1));
            flag=-flag;
        }
       
		/*
		 * for (Iterator<BigInteger> iterator = list.iterator(); iterator.hasNext();) {
		 * System.out.println(iterator.next());
		 * 
		 * }
		 */
        System.out.println("flag:"+flag); 
        BigInteger d;//2
        if (flag==1) {
        	d=list.get(list.size()-2).multiply(BigInteger.ONE).add(BigInteger.ONE);
		}else {
			d=list.get(list.size()-2).multiply(BigInteger.ONE).subtract(BigInteger.ONE);
		}
        for (int i = list.size()-2; i > 0; i--) {
            BigInteger last1=list.get(i);//16
            BigInteger last2=list.get(i-1);//17
                      
            d=last2.multiply(d).add(BigInteger.ONE).divide(last1);
        }
        System.out.println("d:"+d); 
        System.out.println("e*d mod z:"+d.multiply(e).mod(z));
    }
	
	//生成公钥
	public static void publicKey(BigInteger p,BigInteger q) {
		BigInteger n=p.multiply(q);
		BigInteger z=p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
		if (z.mod(BigInteger.valueOf(e)).equals(BigInteger.ZERO)) {
			System.out.println("******************error***********************");
		}
		System.out.println("bits:"+n.bitLength()+",n:"+n);
		System.out.println("e:"+e);
	}
	//生成私钥
	public static void privateKey(BigInteger p,BigInteger q) {
		BigInteger z=p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
		System.out.println("z:"+z);
		int quotient=1;
		while (true) {
			BigInteger zqu=z.multiply(BigInteger.valueOf(quotient)).add(BigInteger.ONE);
			if (zqu.mod(BigInteger.valueOf(e)).equals(BigInteger.ZERO)) {
				
				BigInteger d=zqu.divide(BigInteger.valueOf(e));
				System.out.println("d:"+d);
				System.out.println("quotient:"+quotient);
				
				System.out.println("e*d mod z:"+d.multiply(BigInteger.valueOf(e)).mod(z));
				break;
			}
			quotient++;
		}
		
		
	}
	//公钥加密
	public static void encrypt(BigInteger m,BigInteger n,BigInteger e) {
		BigInteger c=m.modPow(e, n);
		System.out.println("密文："+c);
	}
	//私钥解密
	public static void decrypt(BigInteger c,BigInteger n,BigInteger d) {
		BigInteger m=c.modPow(d, n);
		System.out.println("明文："+m);
	}
	
	//随机生成一个int bits的质数
	public static void getPrime(int bit) {
		
		while (true) {
			BigInteger bigInteger=new BigInteger(bit, random);
			if (bigInteger.bitLength()<(bit-10)) {
				continue;
			}
			//BigInteger bigInteger=new BigInteger("9746347772161");
			PrimeTest primeTest=new PrimeTest(bigInteger);
			if (primeTest.runTest()) {
				System.out.println("质数："+bigInteger);
				//System.out.println(bigInteger.bitLength());
				break;
			}
		}
	}
	
	

}
